import { TreeNode } from "@/基本数据结构/二叉树";

export function serialize(root: TreeNode | null): string {
  if (!root) return '';
  const res: number[] = [];
  const nodeArr: Array<TreeNode | null> = [root];
  while (nodeArr.length) {
    const len = nodeArr.length;
    for (let index = 0; index < len; index++) {
      const node = nodeArr.shift();
      if (!node) {
        res.push(null);
        continue;
      }
      res.push(node.val);
      nodeArr.push(node.left || null);
      nodeArr.push(node.right || null);
    }
  }
  while (res[res.length - 1] === null) {
    res.pop();
  }
  return res.toString();
};
export function deserialize(data: string): TreeNode | null {
  if(!data) return null
  const arr = data.split(',').map((val) => val === '' ? null : Number(val))
  if (!arr || !arr.length) return null;
  const cloneArr = arr.map((val) => val)
  const root = new TreeNode(cloneArr.shift());
  const nodeArr: TreeNode[] = [root];
  while (cloneArr.length) {
      const node = nodeArr.shift();
      for (let index = 0; index < 2; index++) {
          if (!cloneArr.length) break;
          const val = cloneArr.shift();
          if (val === null) continue;
          const temp = new TreeNode(val);
          if (index === 0) {
              node.left = temp;
          } else {
              node.right = temp;
          }
          nodeArr.push(temp);
      }
  }
  return root;
};